Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:

Given 1->2->3->4->5->NULL and k = 2,

return 4->5->1->2->3->NULL.

Solution:

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode(int x) { val = x; }
  7.  * }
  8.  */
  9. public class Solution {
  10.   public ListNode rotateRight(ListNode head, int k) {
  11.     if (head == null) {
  12.       return null;
  13.     }
  15.     int len = getLength(head);
  16.     k %= len;
  18.     if (k == 0) {
  19.       return head;
  20.     }
  22.     ListNode fast = head;
  23.     ListNode slow = head;
  25.     while (fast != null && k > 0) {
  26.       fast = fast.next;
  27.       k--;
  28.     }
  30.     while (fast.next != null) {
  31.       slow = slow.next;
  32.       fast = fast.next;
  33.     }
  35.     fast.next = head;
  36.     head = slow.next;
  37.     slow.next = null;
  39.     return head;
  40.   }
  42.   int getLength(ListNode head) {
  43.     int len = 0;
  44.     while (head != null) {
  45.       head = head.next;
  46.       len++;
  47.     }
  48.     return len;
  49.   }
  50. }